{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Find Mode in Binary Search Tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #tree #depth-first-search #binary-search-tree #binary-tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #树 #深度优先搜索 #二叉搜索树 #二叉树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: findMode"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #二叉搜索树中的众数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个含重复值的二叉搜索树（BST）的根节点 <code>root</code> ，找出并返回 BST 中的所有 <a href=\"https://baike.baidu.com/item/%E4%BC%97%E6%95%B0/44796\" target=\"_blank\">众数</a>（即，出现频率最高的元素）。</p>\n",
    "\n",
    "<p>如果树中有不止一个众数，可以按 <strong>任意顺序</strong> 返回。</p>\n",
    "\n",
    "<p>假定 BST 满足如下定义：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>结点左子树中所含节点的值 <strong>小于等于</strong> 当前节点的值</li>\n",
    "\t<li>结点右子树中所含节点的值 <strong>大于等于</strong> 当前节点的值</li>\n",
    "\t<li>左子树和右子树都是二叉搜索树</li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/03/11/mode-tree.jpg\" style=\"width: 142px; height: 222px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [1,null,2,2]\n",
    "<strong>输出：</strong>[2]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [0]\n",
    "<strong>输出：</strong>[0]\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>树中节点的数目在范围 <code>[1, 10<sup>4</sup>]</code> 内</li>\n",
    "\t<li><code>-10<sup>5</sup> &lt;= Node.val &lt;= 10<sup>5</sup></code></li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>进阶：</strong>你可以不使用额外的空间吗？（假设由递归产生的隐式调用栈的开销不被计算在内）</p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [find-mode-in-binary-search-tree](https://leetcode.cn/problems/find-mode-in-binary-search-tree/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [find-mode-in-binary-search-tree](https://leetcode.cn/problems/find-mode-in-binary-search-tree/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,null,2,2]', '[0]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findMode(self, root: Optional[TreeNode]) -> list[int]:\n",
    "        tree = []\n",
    "        ans = []\n",
    "        def inorder(root):\n",
    "            if not root: return\n",
    "            tree.append(root.val)\n",
    "            inorder(root.left)\n",
    "            inorder(root.right)\n",
    "        inorder(root)\n",
    "        tree_dic = collections.Counter(tree)\n",
    "        maxs = max(tree_dic.values())\n",
    "        for k,v in tree_dic.items():\n",
    "            if v == maxs:\n",
    "                ans.append(k)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def findMode(self, root):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        def dfs(node, p, pc, mp, res):\n",
    "            if not node:\n",
    "                return p, pc, mp, res\n",
    "            p, pc, mp, res = dfs(node.left, p, pc, mp, res)\n",
    "            if node.val == p:\n",
    "                pc += 1\n",
    "            else:\n",
    "                p = node.val\n",
    "                pc = 1\n",
    "            if pc > mp:\n",
    "                mp = pc\n",
    "                res = [p]\n",
    "            elif pc == mp:\n",
    "                res.append(p)\n",
    "            return dfs(node.right, p, pc, mp, res)\n",
    "        return dfs(root, float('-inf'), 0, float('-inf'), [])[-1]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 正确思路：BST中序遍历得到递增序列\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def findMode(self, root):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        self.res = []\n",
    "        if not root:\n",
    "            return self.res\n",
    "        def inorder(root):\n",
    "            if not root:\n",
    "                return\n",
    "            inorder(root.left)\n",
    "            self.res.append(root.val)\n",
    "            inorder(root.right)\n",
    "        inorder(root)\n",
    "        # print(self.res)\n",
    "        max_ = 1\n",
    "        cnt = 1\n",
    "        ret = [self.res[0]]\n",
    "        for i in range(1,len(self.res)):\n",
    "            cnt = cnt+1 if self.res[i]==self.res[i-1] else 1\n",
    "            if(cnt==max_):\n",
    "                ret.append(self.res[i])\n",
    "            if(cnt>max_):\n",
    "                ret = []\n",
    "                ret.append(self.res[i])\n",
    "                max_ = cnt\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def findMode(self, root):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        self.max_count = -1\n",
    "        self.res = []\n",
    "        self.pre = -1\n",
    "        self.count = 0\n",
    "        self.helper(root)\n",
    "        return self.res\n",
    "\n",
    "    def helper(self, root):\n",
    "        if not root:\n",
    "            return\n",
    "        if root:\n",
    "            self.helper(root.left)\n",
    "\n",
    "            if root.val == self.pre:\n",
    "                self.count += 1\n",
    "            else:\n",
    "                self.count = 1\n",
    "                self.pre = root.val\n",
    "\n",
    "            if self.count == self.max_count and root.val != self.res[-1]:\n",
    "                    self.res.append(root.val)\n",
    "\n",
    "            if self.count > self.max_count:\n",
    "                self.max_count = self.count\n",
    "                self.res = []\n",
    "                self.res.append(root.val)\n",
    "        self.helper(root.right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def findMode(self, root: 'TreeNode') -> 'List[int]':\n",
    "        if not root:\n",
    "            return []\n",
    "        c = collections.Counter()\n",
    "        def inorder(root, c):\n",
    "            if not root: return\n",
    "            inorder(root.left, c)\n",
    "            c[root.val] += 1\n",
    "            inorder(root.right, c)\n",
    "        inorder(root, c)\n",
    "        freq = max(c.values())\n",
    "        return [node for node in c if c[node] == freq]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def findMode(self, root):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        if not root:\n",
    "            return []\n",
    "        res = dict()\n",
    "        self.add_count(root, res)\n",
    "        res = sorted(res.items(), key=lambda x:-x[1])\n",
    "        return [x[0] for x in res if x[1] == res[0][1]]\n",
    "    def add_count(self, root, res):\n",
    "        if root:\n",
    "            res[root.val] = res.get(root.val, 0) + 1\n",
    "            self.add_count(root.left, res)\n",
    "            self.add_count(root.right, res)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def bianli(self,root,d):\n",
    "        if  not root :\n",
    "            return []\n",
    "        if root.val not in d:\n",
    "            d[root.val]=1\n",
    "        else:\n",
    "            d[root.val]+=1\n",
    "        self.bianli(root.left,d)\n",
    "        self.bianli(root.right,d)\n",
    "        return d\n",
    "    def findMode(self, root):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        if root is None:\n",
    "            return []\n",
    "        a={}\n",
    "        f=[]\n",
    "        b=self.bianli(root,a)\n",
    "        c=sorted(b.items(),key=lambda x:-x[1])\n",
    "        for d in c:\n",
    "            if d[1]==c[0][1]:\n",
    "                f.append(d[0])\n",
    "        return f\n",
    "\n",
    "       \n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.lst = []\n",
    "    \n",
    "    def solve(self, node):\n",
    "        self.lst.append(node.val)\n",
    "                \n",
    "        if node.left != None:\n",
    "            self.solve(node.left)\n",
    "        \n",
    "        if node.right != None:\n",
    "            self.solve(node.right)\n",
    "    \n",
    "    def findMode(self, root):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        if root == None:\n",
    "            return []\n",
    "        \n",
    "        self.solve(root)\n",
    "        sol = collections.Counter(self.lst).most_common()\n",
    "        n = sol[0][1]\n",
    "        \n",
    "        for i, s in enumerate(sol):\n",
    "            if s[1] != n:\n",
    "                return [x[0] for x in sol[:i]]\n",
    "        \n",
    "        return [x[0] for x in sol]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "     def inOrder(self, root, times):\n",
    "        if not root:\n",
    "            return\n",
    "        self.inOrder(root.left, times)   # 递归遍历左子树\n",
    "        if root.val not in times:  # 若结点值第一次出现，添加新的键值对\n",
    "            times[root.val] = 1\n",
    "        else:  # 不然，次数自增\n",
    "            times[root.val] = times[root.val] + 1\n",
    "        self.inOrder(root.right, times)  # 递归遍历右子树\n",
    "        \n",
    "     def findMode(self, root):\n",
    "        times = dict()\n",
    "        self.inOrder(root, times)\n",
    "        # 按值逆序排序字典\n",
    "        res = sorted(times.items(), key=lambda x:x[1], reverse=True)  \n",
    "        # 返回与最大出现次数(即排序后的第一项)相同的节点值\n",
    "        return [x[0] for x in res if x[1] == res[0][1]]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def findMode(self, root: 'TreeNode') -> 'List[int]':\n",
    "        if not root:\n",
    "            return []\n",
    "        cnt=self.middleSearch(root)\n",
    "        vlist=list(cnt.values())\n",
    "        max_v=max(vlist)\n",
    "        res=[]\n",
    "        for k,v in cnt.items():\n",
    "            if v==max_v:\n",
    "                \n",
    "                res.append(k)\n",
    "        return res\n",
    "        \n",
    "    def middleSearch(self,root):\n",
    "        if not root:\n",
    "            return None,{}\n",
    "        cnt={root.val:1}\n",
    "        if root.left:\n",
    "            left_cnt=self.middleSearch(root.left)\n",
    "            if left_cnt:\n",
    "                for k,v in left_cnt.items():\n",
    "                    if k not in cnt:\n",
    "                        cnt[k]=0\n",
    "                    cnt[k]+=v\n",
    "        if root.right:\n",
    "            right_cnt=self.middleSearch(root.right)\n",
    "        \n",
    "            if right_cnt:\n",
    "                for k,v in right_cnt.items():\n",
    "                    if k not in cnt:\n",
    "                        cnt[k]=0\n",
    "                    cnt[k]+=v\n",
    "        return cnt\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def find(self, root) :\n",
    "        if root == None :\n",
    "            return {}\n",
    "        a = {}\n",
    "        a[root.val] = 1\n",
    "        b=self.find(root.left)\n",
    "        c=self.find(root.right)\n",
    "        \n",
    "        for i in b :\n",
    "            if i in a :\n",
    "                a[i] = a[i] + b[i]\n",
    "            else :\n",
    "                a[i] = b[i]\n",
    "        for i in c :\n",
    "            if i in a :\n",
    "                a[i] = a[i] + c[i]\n",
    "            else :\n",
    "                a[i] = c[i]\n",
    "        return a;\n",
    "        \n",
    "        \n",
    "    def findMode(self, root):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        ma = 0\n",
    "        ve = {}\n",
    "        v = [] \n",
    "        ve = self.find(root)\n",
    "        for i in ve :\n",
    "            ma = max(ma,ve[i])\n",
    "        for i in ve :\n",
    "            if ve[i] == ma :\n",
    "                v.append(i)\n",
    "        return v"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def findMode(self, root: TreeNode) -> List[int]:\n",
    "        if not root:\n",
    "            return []\n",
    "        max_lst = []\n",
    "        count = 0\n",
    "        recent = None\n",
    "        rec_num = 0\n",
    "        stack = [root]\n",
    "        while stack:\n",
    "            node = stack.pop()\n",
    "            if node.left:\n",
    "                tmp = node.left\n",
    "                node.left = None\n",
    "                stack.append(node)\n",
    "                stack.append(tmp)\n",
    "            else:\n",
    "                if node.right:\n",
    "                    stack.append(node.right)\n",
    "                if recent is None:\n",
    "                    recent = node.val\n",
    "                    rec_num += 1\n",
    "                elif recent == node.val:\n",
    "                    rec_num += 1\n",
    "                else:\n",
    "                    if not max_lst or rec_num==count:\n",
    "                        max_lst.append(recent)\n",
    "                        count = rec_num\n",
    "                    elif rec_num>count:\n",
    "                        max_lst = [recent]\n",
    "                        count = rec_num\n",
    "                    recent = node.val\n",
    "                    rec_num = 1\n",
    "        if not max_lst or rec_num==count:\n",
    "            max_lst.append(recent)\n",
    "            count = rec_num\n",
    "        elif rec_num>count:\n",
    "            max_lst = [recent]\n",
    "            count = rec_num \n",
    "        return max_lst\n",
    "\n",
    "\n",
    "\n",
    "            \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def findMode(self, root: TreeNode) -> List[int]:\n",
    "\n",
    "        ans = []\n",
    "\n",
    "        if not root:\n",
    "            return []\n",
    "\n",
    "        def helper(root):\n",
    "\n",
    "            if not root:\n",
    "\n",
    "                return None\n",
    "\n",
    "            root.left = helper(root.left)\n",
    "            ans.append(root.val)\n",
    "            root.right = helper(root.right)\n",
    "        helper(root)\n",
    "        counts = Counter(ans)\n",
    "\n",
    "        tmp = []\n",
    "        maxs = max(counts.values())\n",
    "        for i in counts.keys():\n",
    "            if counts[i] == maxs:\n",
    "                tmp.append(i)\n",
    "\n",
    "        return tmp\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def findMode(self, root: TreeNode) -> List[int]:\n",
    "        self.maxn = 1\n",
    "        self.curn = 1\n",
    "        self.nums = []\n",
    "        self.pre = None\n",
    "        self.inOrder(root)\n",
    "        \n",
    "        return self.nums\n",
    "    \n",
    "    def inOrder(self, root):\n",
    "        if root == None:\n",
    "            return None\n",
    "        self.inOrder(root.left)\n",
    "        if self.pre:\n",
    "            if root.val == self.pre.val:\n",
    "                self.curn += 1\n",
    "            else:\n",
    "                self.curn = 1\n",
    "        \n",
    "        if self.curn > self.maxn:\n",
    "            self.nums = []\n",
    "            self.nums.append(root.val)\n",
    "            self.maxn = self.curn\n",
    "        elif self.curn == self.maxn:\n",
    "            self.nums.append(root.val)\n",
    "        self.pre = root\n",
    "        \n",
    "        self.inOrder(root.right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def findMode(self, root: TreeNode) -> List[int]:\n",
    "\n",
    "        freq = {}\n",
    "\n",
    "        def rec(root):\n",
    "            if root is None:\n",
    "                return\n",
    "            if root.val in freq:\n",
    "                freq[root.val] += 1\n",
    "            else:\n",
    "                freq[root.val] = 1\n",
    "            rec(root.left)\n",
    "            rec(root.right)\n",
    "\n",
    "        rec(root)\n",
    "        max_freq = 0\n",
    "        k_list = []\n",
    "        for k, v in freq.items():\n",
    "            if max_freq == v:\n",
    "                k_list.append(k)\n",
    "            if max_freq < v:\n",
    "                max_freq = v\n",
    "                k_list = [k]\n",
    "        return k_list\n",
    "        \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def findMode(self, root):\n",
    "        if not root:return None\n",
    "        ans,s=[],[]#存储结果\n",
    "        max_num,cur_num=1,1\n",
    "        def midturn(node):#中序遍历\n",
    "            if node: \n",
    "                midturn(node.left)\n",
    "                s.append(node.val)\n",
    "                midturn(node.right)\n",
    "        midturn(root)\n",
    "\n",
    "        ans.append(s[0])#初始化数组\n",
    "        for i in range(1,len(s)):#有序数组求众数，比较当前与前一个的关系，注意范围\n",
    "            if s[i]==s[i-1]:cur_num+=1\n",
    "            else:cur_num=1\n",
    "            if cur_num==max_num:ans.append(s[i])\n",
    "            elif cur_num>max_num:\n",
    "                ans=[]\n",
    "                ans.append(s[i])\n",
    "                max_num=cur_num\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def findMode(self, root: TreeNode) -> List[int]:\n",
    "        self.count = 0\n",
    "        self.maxCount = 0\n",
    "        self.base = None\n",
    "        self.res = []\n",
    "        prev = None\n",
    "\n",
    "        while root:\n",
    "            if root.left:\n",
    "                prev = root.left\n",
    "\n",
    "                while prev.right:\n",
    "                    prev = prev.right\n",
    "                prev.right = root\n",
    "\n",
    "                idx = root\n",
    "                root = root.left\n",
    "                idx.left = None\n",
    "            else:\n",
    "                if root.val == self.base:\n",
    "                    self.count += 1\n",
    "                else:\n",
    "                    self.base = root.val\n",
    "                    self.count = 1\n",
    "                \n",
    "                if self.count > self.maxCount:\n",
    "                    self.maxCount = self.count\n",
    "                    self.res = [root.val]\n",
    "                elif self.count == self.maxCount:\n",
    "                    self.res.append(root.val)\n",
    "\n",
    "                root = root.right\n",
    "        \n",
    "        return self.res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findMode(self, root: TreeNode) -> List[int]:\n",
    "        res = []\n",
    "        pre = None\n",
    "        curr_node_val = math.inf\n",
    "        curr_count = 0\n",
    "        max_count = 0\n",
    "        while root:\n",
    "            # 如果左节点不为空，就将当前节点连带右子树全部挂到\n",
    "            # 左节点的最右子树下面\n",
    "            if root.left:\n",
    "                pre = root.left\n",
    "                while pre.right:\n",
    "                    pre = pre.right\n",
    "                pre.right = root\n",
    "                tmp = root\n",
    "                root = root.left\n",
    "                tmp.left = None\n",
    "            # 左子树为空，则打印这个节点，并向右边遍历\n",
    "            else:\n",
    "                if curr_node_val == math.inf:\n",
    "                    curr_node_val = root.val\n",
    "                    curr_count += 1\n",
    "                else:\n",
    "                    if curr_node_val == root.val:\n",
    "                        curr_count +=1\n",
    "                    elif curr_node_val != root.val:\n",
    "                        curr_count = 1\n",
    "                        curr_node_val = root.val\n",
    "                if curr_count > max_count:\n",
    "                    max_count = curr_count\n",
    "                    curr_node_val = root.val\n",
    "                    res = [curr_node_val]\n",
    "                elif curr_count == max_count:\n",
    "                    res.append(curr_node_val)\n",
    "                root = root.right\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findMode(self, root: Optional[TreeNode]) -> List[int]:\n",
    "        if not root:\n",
    "            return \n",
    "        dict={}\n",
    "        stack=[root]\n",
    "        while stack:\n",
    "            node=stack[-1]\n",
    "            if node.left:\n",
    "                stack.append(node.left)\n",
    "                node.left=None\n",
    "            else:\n",
    "                node=stack.pop()\n",
    "                if node.val in dict:\n",
    "                    dict[node.val]+=1\n",
    "                else:\n",
    "                    dict[node.val]=1\n",
    "                \n",
    "                if node.right:\n",
    "                    stack.append(node.right)\n",
    "        max_=max(dict.values())\n",
    "        ans=[]\n",
    "        for key in dict.keys():\n",
    "            if dict[key]==max_:\n",
    "                ans.append(key)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findMode(self, root: Optional[TreeNode]) -> List[int]:\n",
    "        lst = []\n",
    "        result = []\n",
    "        def inorder(root):\n",
    "            if root:\n",
    "                root.left = inorder(root.left)\n",
    "                lst.append(root.val)\n",
    "                root.right = inorder(root.right)\n",
    "                return \n",
    "        inorder(root)\n",
    "\n",
    "        count = 1\n",
    "        maxCount = 1\n",
    "        pre = lst[0]\n",
    "        result.append(pre)\n",
    "\n",
    "        for i in range(1,len(lst)):\n",
    "            if pre == lst[i]:\n",
    "                count += 1\n",
    "            else:\n",
    "                count = 1\n",
    "            if count == maxCount:\n",
    "                result.append(lst[i])\n",
    "            if count > maxCount:\n",
    "                maxCount = count\n",
    "                result = [lst[i]]\n",
    "            pre = lst[i]\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findMode(self, root: Optional[TreeNode]) -> List[int]:\n",
    "        result = []\n",
    "\n",
    "        \n",
    "        maxCount = 1\n",
    "        count = 1\n",
    "        \n",
    "\n",
    "\n",
    "        def inorder(root):\n",
    "            if not root:\n",
    "                return None\n",
    "            if root.left: root.left = inorder(root.left)\n",
    "            result.append(root.val)\n",
    "            if root.right: root.right = inorder(root.right)\n",
    "            return result\n",
    "\n",
    "        inorder(root)\n",
    "\n",
    "        pre = result[0]\n",
    "        lst = [pre]\n",
    "\n",
    "        for i in range(1,len(result)):\n",
    "            if result[i]==pre:\n",
    "                count+=1\n",
    "            else:\n",
    "                count = 1\n",
    "            if count == maxCount:\n",
    "                lst.append(result[i])\n",
    "            if count > maxCount:\n",
    "                maxCount = count\n",
    "                lst = [result[i]]\n",
    "            pre = result[i]\n",
    "        return lst\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findMode(self, root: Optional[TreeNode]) -> List[int]:\n",
    "        lst = []\n",
    "        def build(root):\n",
    "            if not root:\n",
    "                return []\n",
    "            root.left = build(root.left)\n",
    "            lst.append(root.val)\n",
    "            root.right = build(root.right)\n",
    "            return lst\n",
    "\n",
    "        build(root)\n",
    "        ans = []\n",
    "        res = Counter(lst).most_common()\n",
    "        for k, v in res:\n",
    "            if v == res[0][1]:\n",
    "                ans.append(k)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findMode(self, root: TreeNode) -> List[int]:\n",
    "        \n",
    "        res = []\n",
    "        count = 0\n",
    "        max_count=0\n",
    "        pre_val = None\n",
    "        \n",
    "        def dfs(root):\n",
    "            nonlocal count, max_count, pre_val, res\n",
    "            if root==None: return \n",
    "            # 左\n",
    "            dfs(root.left)\n",
    "            # 中\n",
    "            if pre_val==None: # 记录第一个节点\n",
    "                count=1\n",
    "            elif root.val==pre_val:\n",
    "                count += 1\n",
    "            else:\n",
    "                count=1\n",
    "            \n",
    "            if count==max_count:\n",
    "                res.append(root.val)\n",
    "            elif count>max_count:\n",
    "                max_count = count\n",
    "                res = [root.val]\n",
    "            \n",
    "            # 更新上一记录节点\n",
    "            pre_val = root.val\n",
    "\n",
    "            # 右\n",
    "            dfs(root.right)\n",
    "\n",
    "        \n",
    "        dfs(root)\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findMode(self, root: Optional[TreeNode]) -> List[int]:\n",
    "        stk = deque()\n",
    "        #nums = []\n",
    "        #map_dict = {}\n",
    "\n",
    "        res = []\n",
    "        pre_node = None\n",
    "        max_count = 0\n",
    "        k = 0\n",
    "        if not root:\n",
    "            return res\n",
    "\n",
    "        if root:\n",
    "            stk.append(root)\n",
    "\n",
    "        while stk:\n",
    "            node = stk.pop()\n",
    "            left_node = node.left\n",
    "            node.left = None\n",
    "            if not left_node:\n",
    "                if not pre_node:\n",
    "                    k = 1\n",
    "                    pre_node = node\n",
    "                else:\n",
    "                    if node.val == pre_node.val:\n",
    "                        k += 1\n",
    "                    else:\n",
    "                        if k == max_count:\n",
    "                            res.append(pre_node.val)\n",
    "                        if k > max_count:\n",
    "                            max_count = k\n",
    "                            res = []\n",
    "                            res.append(pre_node.val)\n",
    "                        pre_node = node\n",
    "                        k = 1\n",
    "\n",
    "                #nums.append(node.val)\n",
    "                if node.right:\n",
    "                    stk.append(node.right)\n",
    "            else:\n",
    "                stk.append(node)\n",
    "                stk.append(left_node)\n",
    "\n",
    "\n",
    "        if k == max_count:\n",
    "            res.append(pre_node.val)\n",
    "        if k > max_count:\n",
    "            res = []\n",
    "            res.append(pre_node.val)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.most = 0\n",
    "        self.number = 0\n",
    "        self.res = []\n",
    "        self.pre = None\n",
    "\n",
    "    def findMode(self, root: Optional[TreeNode]) -> List[int]:\n",
    "        \"\"\"利用二叉树的有序性(递归：中序遍历)\"\"\"\n",
    "        if not root:\n",
    "            return\n",
    "        \n",
    "        self.findMode(root.left)  # 左\n",
    "\n",
    "        if not self.pre:  # 第一个节点\n",
    "            self.number = 1\n",
    "        else:\n",
    "            if root.val == self.pre.val:\n",
    "                self.number += 1\n",
    "            else:\n",
    "                self.number = 1\n",
    "        if self.number == self.most:\n",
    "            self.res.append(root.val)\n",
    "        elif self.number > self.most:\n",
    "            self.res.clear()\n",
    "            self.res.append(root.val)\n",
    "            self.most = self.number\n",
    "        self.pre = root\n",
    "        \n",
    "        self.findMode(root.right)  # 右\n",
    "        \n",
    "        return self.res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "from collections import Counter\n",
    "class Solution:\n",
    "    def inorder(self,root):\n",
    "        if not root:\n",
    "            return []\n",
    "        root.left =self.inorder(root.left)\n",
    "        root.right = self.inorder(root.right)\n",
    "        return root.left+[root.val]+root.right\n",
    "    def findMode(self, root: Optional[TreeNode]) -> List[int]:\n",
    "        inorder =self.inorder(root)\n",
    "        map = Counter(inorder)\n",
    "        max_count = max(map.values())\n",
    "        mode = [x for x, count in map.items() if count == max_count]\n",
    "        return mode"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def getlist(self, root, a):\n",
    "        if root.left:\n",
    "            self.getlist(root.left,a)\n",
    "        a.append(root.val)\n",
    "        if root.right:\n",
    "            self.getlist(root.right,a)\n",
    "        return a\n",
    "\n",
    "    def findMode(self, root: Optional[TreeNode]) -> List[int]:\n",
    "        a=[]\n",
    "        if root==None:\n",
    "            return a\n",
    "        a=self.getlist(root,a)\n",
    "        print(a)\n",
    "        maxcount=0\n",
    "        count=0\n",
    "        mm=[]\n",
    "        pre=a[0]\n",
    "        if len(a)==1:\n",
    "            return a\n",
    "        for i in a[1:]:\n",
    "            if i==pre:\n",
    "                count+=1\n",
    "            else:\n",
    "                count=0\n",
    "            pre=i\n",
    "            if count==maxcount:\n",
    "                mm.append(i)\n",
    "            if count>maxcount:\n",
    "                maxcount=count\n",
    "                mm=[]\n",
    "                mm.append(i)\n",
    "        if maxcount==0:\n",
    "            mm.append(a[0])\n",
    "        return mm\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findMode(self, root: Optional[TreeNode]) -> List[int]:\n",
    "        # 迭代法中序遍历BST\n",
    "        stack,res = [],[]       # 栈、保存遍历结果\n",
    "        while root or stack:\n",
    "            if root:\n",
    "                stack.append(root)\n",
    "                root = root.left\n",
    "            else:\n",
    "                root = stack.pop()\n",
    "                res.append(root.val)\n",
    "                root = root.right\n",
    "        \n",
    "        ans = []            # 保存结果\n",
    "        my_set = list(set(res))   # 集合\n",
    "        count_list = []     # 保存集合中每个数字的个数\n",
    "\n",
    "        for num in my_set:\n",
    "            count_list.append(res.count(num))\n",
    "        \n",
    "        max_count = max(count_list)\n",
    "        for i in range(len(count_list)):\n",
    "            if count_list[i] == max_count:\n",
    "                ans.append(my_set[i])\n",
    "\n",
    "        return ans\n",
    "\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "\n",
    "# 递归 3 中序遍历求众数 不使用额外空间\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.pre = None\n",
    "        self.cnt = 1\n",
    "        self.max_freq = 1\n",
    "        self.res = []\n",
    "\n",
    "    def findMode(self, root: Optional[TreeNode]) -> List[int]:\n",
    "        def traversal(node):\n",
    "            if node is None:\n",
    "                return\n",
    "            traversal(node.left)\n",
    "            if self.pre is None:\n",
    "                self.cnt = 1\n",
    "            elif self.pre.val == node.val:\n",
    "                self.cnt += 1\n",
    "            else:\n",
    "                self.cnt = 1\n",
    "\n",
    "            if self.cnt == self.max_freq:\n",
    "                self.res.append(node.val)\n",
    "            elif self.cnt > self.max_freq:\n",
    "                self.res = [node.val]\n",
    "                self.max_freq = self.cnt\n",
    "            self.pre = node\n",
    "            traversal(node.right)\n",
    "\n",
    "        traversal(root)\n",
    "        return self.res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findMode(self, root: Optional[TreeNode]) -> List[int]:\n",
    "        result = []\n",
    "        count = 0\n",
    "        max_count = 0\n",
    "        pre = None\n",
    "        st = [root]\n",
    "        while st:\n",
    "            node = st.pop()\n",
    "            if node:\n",
    "                if node.right:\n",
    "                    st.append(node.right)\n",
    "                st.append(node)\n",
    "                st.append(None)\n",
    "                if node.left:\n",
    "                    st.append(node.left)\n",
    "            else:\n",
    "                node = st.pop()\n",
    "                if pre and node.val == pre.val:\n",
    "                    count += 1\n",
    "                else:\n",
    "                    count = 1\n",
    "                if count > max_count:\n",
    "                    max_count = count\n",
    "                    result = [node.val]\n",
    "                elif count == max_count:\n",
    "                    result.append(node.val)\n",
    "                pre = node\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.pre = None\n",
    "        self.ret = []\n",
    "        self.ret_count, self.max_count, self.cur_count = 0, 0, 0\n",
    "\n",
    "    def findMode(self, root: TreeNode) -> List[int]:\n",
    "        self.inOrder(root)\n",
    "        self.pre = None\n",
    "        self.ret = [0] * self.ret_count\n",
    "        self.ret_count, self.cur_count = 0, 0\n",
    "        self.inOrder(root)\n",
    "        return self.ret\n",
    "\n",
    "    def inOrder(self, root: TreeNode) -> None:\n",
    "        if not root:\n",
    "            return\n",
    "        self.inOrder(root.left)\n",
    "        if self.pre and self.pre.val == root.val:\n",
    "            self.cur_count += 1\n",
    "        else:\n",
    "            self.cur_count = 1\n",
    "        if self.cur_count > self.max_count:\n",
    "            self.max_count = self.cur_count\n",
    "            self.ret_count = 1\n",
    "        elif self.cur_count == self.max_count:\n",
    "            if len(self.ret):\n",
    "                self.ret[self.ret_count] = root.val\n",
    "            self.ret_count += 1\n",
    "        self.pre = root\n",
    "        self.inOrder(root.right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.pre = None\n",
    "        self.ret = []\n",
    "        self.ret_count, self.max_count, self.cur_count = 0, 0, 0\n",
    "\n",
    "    def findMode(self, root: TreeNode) -> List[int]:\n",
    "        self.inOrder(root)\n",
    "        self.pre = None\n",
    "        self.ret = [0] * self.ret_count\n",
    "        self.ret_count, self.cur_count = 0, 0\n",
    "        self.inOrder(root)\n",
    "        return self.ret\n",
    "\n",
    "    def inOrder(self, root: TreeNode) -> None:\n",
    "        if not root:\n",
    "            return\n",
    "        self.inOrder(root.left)\n",
    "        if self.pre and self.pre.val == root.val:\n",
    "            self.cur_count += 1\n",
    "        else:\n",
    "            self.cur_count = 1\n",
    "        if self.cur_count > self.max_count:\n",
    "            self.max_count = self.cur_count\n",
    "            self.ret_count = 1\n",
    "        elif self.cur_count == self.max_count:\n",
    "            if len(self.ret):\n",
    "                self.ret[self.ret_count] = root.val\n",
    "            self.ret_count += 1\n",
    "        self.pre = root\n",
    "        self.inOrder(root.right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def traversal(self, root):\n",
    "        if not root:\n",
    "            return []\n",
    "        left = self.traversal(root.left)\n",
    "        right = self.traversal(root.right)\n",
    "        return left + [root.val] + right\n",
    "\n",
    "    def findMode(self, root: Optional[TreeNode]) -> List[int]:\n",
    "        results_dic = {}\n",
    "        results_val = []\n",
    "        max_freq = 0\n",
    "        results = self.traversal(root)\n",
    "        for num in results:\n",
    "            if num not in results_dic:\n",
    "                results_dic[num] = 1\n",
    "            else:\n",
    "                results_dic[num] += 1\n",
    "        max_freq = max(results_dic.values())\n",
    "        for key,freq in results_dic.items():\n",
    "            if freq == max_freq:\n",
    "                results_val.append(key)\n",
    "\n",
    "        return results_val\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
